#define _CRT_SECURE_NO_WARNINGS 1
//用队列解决二叉树的层序遍历和判断二叉树是否是完全二叉树
//队列存树的节点
#include "BinaryTree.h"
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	assert(root);
	Queue queue;
	QueueInit(&queue);
	//入根
	if (root != NULL)
	{
		QueuePush(&queue, root);
	}
	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);
		printf("%d " , front->val);
		
		//入左子树 空不用入
		if ((front->left)!=NULL)
		{
			QueuePush(&queue, front->left);
		}
		//入右子树
		if ((front->right)!=NULL)
		{
			QueuePush(&queue, front->right);
		}
		QueuePop(&queue);
	}
	QueueDestory(&queue);
	
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	assert(root);
	Queue queue;
	QueueInit(&queue);
	//入根
	if (root != NULL)
	{
		QueuePush(&queue, root);
	}
	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);
		//遍历遇到空结点就跳出循环 进行下一步判断
		if (front == NULL)
			break;
		//入左 右子树 空也要入
		QueuePush(&queue, front->left);
		QueuePush(&queue, front->right);
		QueuePop(&queue);
	}
	//完全二叉树到这 后面全部为NULL 
	//后面如果还有非空结点 则不是完全二叉树 销毁队列返回false
	while (!QueueEmpty(&queue))
	{
		BTNode* front = QueueFront(&queue);
		QueuePop(&queue);
		if (front)
		{
			QueueDestory(&queue);
			return false;
		}
	}

	QueueDestory(&queue);
	return true;

}

// 创建树的新节点
BTNode* BuyNewNode(int x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}

	newnode->val = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}
int main()
{
	
	BTNode* node1 = BuyNewNode(1);
	BTNode* node2 = BuyNewNode(2);
	BTNode* node3 = BuyNewNode(3);
	BTNode* node4 = BuyNewNode(4);
	BTNode* node5 = BuyNewNode(5);
	BTNode* node6 = BuyNewNode(6);
	BTNode* node7 = BuyNewNode(7);

	node1->left = node2;
	node2->left = node4;
	node1->right = node3;
	node3->left = node5;
	node3->right = node6;
	node6->left = node7;



	
	BinaryTreeLevelOrder(node1);

	printf("%d", BinaryTreeComplete(node1));
	return 0;
}